import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2023-01-18
 * Time:20:25
 */
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < stones.length; i++) {
            priorityQueue.offer(stones[i]);
        }
        while (priorityQueue.size() > 1) {
            int max = priorityQueue.poll();
            int min = priorityQueue.poll();
            priorityQueue.offer(max - min);
        }
        return priorityQueue.peek();
    }

}

public class Test {
    //    public static void sortColors(int[] nums) {
//        int head=0;
//        int tail=nums.length-1;
//        while(head<tail){
//            while(nums[head]!=2&&head<tail){
//                head++;
//            }
//            if(nums[head]==2){
//                int tmp=nums[head];
//                nums[head]=nums[tail];
//                nums[tail]=tmp;
//                tail--;
//            }
//        }
//        head=0;
//        while(head<tail){
//            while(nums[head]!=1&&head<tail) {
//                head++;
//            }
//            if(nums[head]==1){
//                if(nums[tail]==0){
//                    break;
//                }
//                int tmp=nums[head];
//                nums[head]=nums[tail];
//                nums[tail]=tmp;
//                tail--;
//            }
//        }
//    }
    public static void sortColors(int[] nums) {
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                num0++;
            } else if (nums[i] == 1) {
                num1++;
            } else {
                num2++;
            }
        }
        int i = 0;
        while (num0 > 0) {
            nums[i++] = 0;
            num0--;
        }
        while (num1 > 0) {
            nums[i++] = 1;
            num1--;
        }
        while (num2 > 0) {
            nums[i++] = 2;
            num2--;
        }
    }

    public static void sortColors1(int[] nums) {
        int head = 0;
        int tail = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (i > tail) {
                break;
            }
            if (nums[i] == 2) {
                int tmp = nums[tail];
                nums[tail] = nums[i];
                nums[i] = tmp;
                tail--;
                i--;
            } else {
                if (nums[i] == 0) {
                    int tmp = nums[head];
                    nums[head] = nums[i];
                    nums[i] = tmp;
                    head++;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 2};
        sortColors1(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void main1(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        priorityQueue.add(1);
        priorityQueue.add(2);
        System.out.println(priorityQueue.peek());
        priorityQueue.size();
        int[] arr = new int[2];
        for (int i = 0; i < arr.length; i++) {

        }
    }
}
